package com.example.demo.arithmetic.datastructure.linkedlist2;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

//给你一个单链表的头节点 head ，请你判断该链表是否为
//回文链表
//。如果是，返回 true ；否则，返回 false 。
public class Leetcode234 {
    public static void main(String[] args) {
//        ListNode head1 = new ListNode(1, null);
        ListNode head2 = new ListNode(4, null);
        ListNode head3 = new ListNode(2, head2);
        ListNode head4 = new ListNode(2, head3);
        ListNode head5 = new ListNode(1, head4);
        ListNode b = new Leetcode234().reverseList(head5);
//        boolean b = new Leetcode234().isPalindrome(head5);
        System.out.println(b.val);

    }


    public boolean isPalindrome(ListNode head) {
        // 找到中间节点
        ListNode p1 = head, p2 = head;
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        ListNode mid = p1;
        //System.out.println(mid.val);
        // 反转mid开头的链表 实际上后半部分
        // 创建新链表
        ListNode n1 = null;
        ListNode p = mid;
        while (p != null) {
            n1 = new ListNode(p.val, n1);
            p = p.next;
        }
        ListNode newHead = n1;
        //        System.out.println(newHead.val);
        while (newHead != null) {
            int val = newHead.val;
            if (val != head.val) {
                return false;
            }

            newHead = newHead.next;
            head = head.next;
        }


        return true;
    }

    /**
     * 链表反转
     *
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            // 先存储后一个节点
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;

    }

    /**
     * 链表反转
     *
     * @param
     * @return
     */
    public ListNode reverseList3(ListNode o1) {
        // 创建新链表
        List list1 = new List(o1);
        List list2 = new List(null);
        while (true) {
            ListNode first = list1.removeFirst();
            if (first == null) {
                break;
            }
            list2.addFirst(first);
        }

        return list2.head;
    }

    /**
     * 链表反转
     *
     * @param
     * @return
     */
    public ListNode reverseList5(ListNode o1) {
        if (o1 == null || o1.next == null) {
            return o1;
        }
        ListNode last = reverseList5(o1.next);
        o1.next.next = o1;
        o1.next = null;
        return last;
    }


    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }


    static class List {
        ListNode head;

        public List(ListNode head) {
            this.head = head;
        }


        public void addFirst(ListNode first) {
            // 待添加的节点下一节点 指向当前头部
            first.next = head;
            // first作为新的头节点
            head = first;
        }

        public ListNode removeFirst() {
            ListNode first = head;
            if (first != null) {
                head = first.next;
            }
            return first;
        }
    }


}
